Coding Scheme

A way to use a channel. Better if error can be recovered.

Model

$$ W \to \boxed{\mathcal{E}} \overset{X^n}{\to} \underset{\text{Channel}}{\boxed{\mathcal{X} \to \boxed{P[Y|X]} \to \mathcal{Y}}} \overset{Y^n}{\to} \boxed{\mathcal{D}} \to \hat{W} $$

Definition

A coding scheme $(M, n)$ consists of:

Rate

It has a innate corresponding property called rate. The rate of a $(M, n)​$ coding scheme is defined as: $$ \begin{aligned} R = \frac{\log_2 M}{n} &= \frac{\text{The “true” amount of information of each message}}{\text{Bits sent each time}} (\text{bits/channel$\cdot$time}) \\ &= \text{“True” amount of information each sent bit carries} \end{aligned} $$ Note that $M$ and $R$ are interchangeable: $$ M \overset{n}{\Leftrightarrow} R $$ So an $(M, n)$ coding scheme can also be written as a $(2^{nR}, n)$ coding scheme.

Metrics

Conditional Probability of Error: $$ P_e^{(n)} (w) = P[\hat{W} \neq W | W = w] $$ Average Probability of Error: $$ \begin{aligned} P_{e}^{(n)} = \frac{1}{M} \sum_{i=1}^{M} P_e^{(n)}(w) \end{aligned} $$

Maximum Probability of Error: $$ \begin{aligned} P_{e, \max}^{(n)} = \max_{w} P_e^{(n)}(w) \end{aligned} $$

Interpretation

$$ \begin{aligned} (M, n) &= (\text{Amount of possible messages}, \text{\#Bits sent each time}) \\ &= (2^{\text{\#Bits belonging to the message}}, \text{\#Bits sent}) \end{aligned} $$

by Jon